package com.heima.algorithm.sort;

import java.util.ArrayList;

/**
 * <h3>基数排序 最低有效数字LSD(Least significant digit)</h3>
 * <ol>
 *     <li>当需要排序的内容是电话号码或者身份证号这种大的id时，一般就会用基数排序</li>
 *     <li>这些一般都是用字符串存的，而且一般来说都是等长的</li>
 *     <li>从低位到高位一位一位的桶排序，这里的实现默认这些字符都是ASCII编码范围内</li>
 *     <li>为什么说最低有效数字，意思是，越往前优先级越高（高位优先级高），那么前面的就应该稍后排</li>
 * </ol>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/6 12:02
 */
public class RadixSort {
    //（1）非比较的排序算法
    //（2）时间复杂度：O(d * (N + K))，空间复杂度：O(N + K)，其中d为基数位数，N是数组大小，K是桶的数量，稳定：是

    private final static int BUCKET_SIZE = 128; // 桶的个数

    /**
     * 基数排序，这里默认是按照字符串的最短长度来排序
     * @param arr 待排序的字符串数组
     */
    public static void radixSort(String[] arr) {
        // 找到数组中最短的字符串的长度
        int minLength = arr[0].length();
        for (int i = 1; i < arr.length; i++) {
            if (arr[i].length() < minLength){
                minLength = arr[i].length();
            }
        }
        // 基数排序
        radixSort(arr, minLength);
    }

    /**
     * 基数排序，从最低有效位开始，依次对每一位进行桶排序
     * @param arr 待排序的字符串数组
     * @param length 指定要排序范围的长度
     */
    public static void radixSort(String[] arr, int length) {
        // 创建桶
        ArrayList<ArrayList<String>> bucketList = new ArrayList<>(BUCKET_SIZE);
        // 初始化桶
        for (int i = 0; i < BUCKET_SIZE; i++) {
            bucketList.add(new ArrayList<>());
        }
        // 从低到高，将字符串的每一位都进行一次桶排序
        for (int i = length - 1; i >= 0; i--) {
            // 遍历数组，将元素放入桶中
            for (String s : arr) {
                bucketList.get(s.charAt(i)).add(s);
            }
            // 遍历桶，将桶中的元素放回数组中
            int index = 0;
            for (ArrayList<String> bucket : bucketList) {
                for (String s : bucket) {
                    arr[index++] = s;
                }
            }
            // 清空每个桶的内容
            for (ArrayList<String> bucket : bucketList) {
                bucket.clear();
            }
        }
    }
}
